java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested4.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 15:15:02,172 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 15:15:02,175 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 15:15:02,189 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 15:15:02,189 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 15:15:02,190 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 15:15:02,191 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 15:15:02,195 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 15:15:02,198 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 15:15:02,198 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 15:15:02,199 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 15:15:02,199 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 15:15:02,200 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 15:15:02,203 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 15:15:02,204 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 15:15:02,204 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 15:15:02,214 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 15:15:02,216 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 15:15:02,217 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 15:15:02,218 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 15:15:02,219 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 15:15:02,224 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 15:15:02,224 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 15:15:02,224 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 15:15:02,225 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 15:15:02,226 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 15:15:02,230 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 15:15:02,230 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 15:15:02,231 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 15:15:02,232 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 15:15:02,237 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 15:15:02,238 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 15:15:02,238 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 15:15:02,239 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 15:15:02,239 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 15:15:02,240 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 15:15:02,252 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 15:15:02,253 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 15:15:02,253 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 15:15:02,253 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 15:15:02,256 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 15:15:02,256 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 15:15:02,257 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 15:15:02,257 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 15:15:02,257 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 15:15:02,257 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 15:15:02,257 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:15:02,258 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 15:15:02,258 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 15:15:02,258 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 15:15:02,258 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 15:15:02,258 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 15:15:02,259 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 15:15:02,259 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 15:15:02,259 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 15:15:02,260 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 15:15:02,260 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 15:15:02,316 INFO ]: Repository-Root is: /tmp [2018-06-22 15:15:02,333 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 15:15:02,335 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 15:15:02,337 INFO ]: Initializing SmtParser... [2018-06-22 15:15:02,337 INFO ]: SmtParser initialized [2018-06-22 15:15:02,337 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested4.c.smt2 [2018-06-22 15:15:02,339 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 15:15:02,411 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested4.c.smt2 unknown [2018-06-22 15:15:02,652 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/nested4.c.smt2 [2018-06-22 15:15:02,657 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 15:15:02,663 INFO ]: Walking toolchain with 4 elements. [2018-06-22 15:15:02,663 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 15:15:02,663 INFO ]: Initializing ChcToBoogie... [2018-06-22 15:15:02,663 INFO ]: ChcToBoogie initialized [2018-06-22 15:15:02,667 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:15:02" (1/1) ... [2018-06-22 15:15:02,707 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:15:02 Unit [2018-06-22 15:15:02,707 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 15:15:02,707 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 15:15:02,707 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 15:15:02,707 INFO ]: Boogie Preprocessor initialized [2018-06-22 15:15:02,734 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:15:02" (1/1) ... [2018-06-22 15:15:02,734 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:15:02" (1/1) ... [2018-06-22 15:15:02,743 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:15:02" (1/1) ... [2018-06-22 15:15:02,743 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:15:02" (1/1) ... [2018-06-22 15:15:02,747 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:15:02" (1/1) ... [2018-06-22 15:15:02,761 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:15:02" (1/1) ... [2018-06-22 15:15:02,762 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:15:02" (1/1) ... [2018-06-22 15:15:02,764 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 15:15:02,765 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 15:15:02,765 INFO ]: Initializing RCFGBuilder... [2018-06-22 15:15:02,765 INFO ]: RCFGBuilder initialized [2018-06-22 15:15:02,766 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:15:02" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 15:15:02,788 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 15:15:02,788 INFO ]: Found specification of procedure False [2018-06-22 15:15:02,788 INFO ]: Found implementation of procedure False [2018-06-22 15:15:02,788 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 15:15:02,788 INFO ]: Found specification of procedure state [2018-06-22 15:15:02,788 INFO ]: Found implementation of procedure state [2018-06-22 15:15:02,788 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 15:15:02,789 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 15:15:02,789 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 15:15:03,084 INFO ]: Using library mode [2018-06-22 15:15:03,084 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:15:03 BoogieIcfgContainer [2018-06-22 15:15:03,084 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 15:15:03,085 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 15:15:03,085 INFO ]: Initializing TraceAbstraction... [2018-06-22 15:15:03,092 INFO ]: TraceAbstraction initialized [2018-06-22 15:15:03,092 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 03:15:02" (1/3) ... [2018-06-22 15:15:03,094 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@18a66e7b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 03:15:03, skipping insertion in model container [2018-06-22 15:15:03,094 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 03:15:02" (2/3) ... [2018-06-22 15:15:03,094 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@18a66e7b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 03:15:03, skipping insertion in model container [2018-06-22 15:15:03,094 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 03:15:03" (3/3) ... [2018-06-22 15:15:03,096 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 15:15:03,110 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 15:15:03,126 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 15:15:03,164 INFO ]: Using default assertion order modulation [2018-06-22 15:15:03,165 INFO ]: Interprodecural is true [2018-06-22 15:15:03,165 INFO ]: Hoare is false [2018-06-22 15:15:03,165 INFO ]: Compute interpolants for FPandBP [2018-06-22 15:15:03,165 INFO ]: Backedges is TWOTRACK [2018-06-22 15:15:03,165 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 15:15:03,165 INFO ]: Difference is false [2018-06-22 15:15:03,165 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 15:15:03,165 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 15:15:03,178 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 15:15:03,186 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 15:15:03,186 INFO ]: Found error trace [2018-06-22 15:15:03,187 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:15:03,187 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:15:03,191 INFO ]: Analyzing trace with hash -597537630, now seen corresponding path program 1 times [2018-06-22 15:15:03,192 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:15:03,193 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:15:03,224 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:03,224 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:15:03,224 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:03,257 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:03,359 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 15:15:03,362 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 15:15:03,362 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 15:15:03,364 INFO ]: Interpolant automaton has 4 states [2018-06-22 15:15:03,377 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 15:15:03,378 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:15:03,379 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 15:15:03,458 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:15:03,459 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 15:15:03,459 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 15:15:03,460 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 15:15:03,460 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:15:03,469 INFO ]: With dead ends: 13 [2018-06-22 15:15:03,469 INFO ]: Without dead ends: 13 [2018-06-22 15:15:03,471 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 15:15:03,483 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 15:15:03,505 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 15:15:03,506 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 15:15:03,507 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 15:15:03,508 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 15:15:03,508 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:15:03,508 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 15:15:03,508 INFO ]: Interpolant automaton has 4 states. [2018-06-22 15:15:03,508 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 15:15:03,509 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 15:15:03,510 INFO ]: Found error trace [2018-06-22 15:15:03,510 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:15:03,510 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:15:03,510 INFO ]: Analyzing trace with hash 1530833734, now seen corresponding path program 1 times [2018-06-22 15:15:03,510 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:15:03,510 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:15:03,511 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:03,511 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:15:03,511 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:03,557 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:03,743 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:15:03,743 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:15:03,743 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:15:03,753 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:15:03,780 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:03,790 INFO ]: Computing forward predicates... [2018-06-22 15:15:04,021 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 15:15:04,042 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:15:04,042 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-22 15:15:04,043 INFO ]: Interpolant automaton has 6 states [2018-06-22 15:15:04,043 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-22 15:15:04,043 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:15:04,043 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 6 states. [2018-06-22 15:15:04,179 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:15:04,180 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 15:15:04,181 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 15:15:04,181 INFO ]: Start accepts. Automaton has 6 states. Word has length 13 [2018-06-22 15:15:04,181 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:15:04,182 INFO ]: With dead ends: 15 [2018-06-22 15:15:04,182 INFO ]: Without dead ends: 15 [2018-06-22 15:15:04,183 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-22 15:15:04,183 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 15:15:04,185 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 15:15:04,185 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 15:15:04,188 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 15:15:04,188 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 15:15:04,188 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:15:04,188 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 15:15:04,188 INFO ]: Interpolant automaton has 6 states. [2018-06-22 15:15:04,188 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 15:15:04,189 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 15:15:04,189 INFO ]: Found error trace [2018-06-22 15:15:04,189 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:15:04,189 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:15:04,189 INFO ]: Analyzing trace with hash -1486246934, now seen corresponding path program 2 times [2018-06-22 15:15:04,189 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:15:04,189 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:15:04,190 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:04,190 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:15:04,190 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:04,257 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:04,554 WARN ]: Spent 124.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 12 [2018-06-22 15:15:04,667 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:15:04,667 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:15:04,667 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:15:04,683 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 15:15:04,737 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 15:15:04,737 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:04,740 INFO ]: Computing forward predicates... [2018-06-22 15:15:05,136 WARN ]: Spent 185.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 7 [2018-06-22 15:15:05,581 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 15:15:05,601 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:15:05,601 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-22 15:15:05,601 INFO ]: Interpolant automaton has 11 states [2018-06-22 15:15:05,602 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-22 15:15:05,602 INFO ]: CoverageRelationStatistics Valid=29, Invalid=81, Unknown=0, NotChecked=0, Total=110 [2018-06-22 15:15:05,602 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 11 states. [2018-06-22 15:15:05,885 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:15:05,885 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-22 15:15:05,886 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-22 15:15:05,886 INFO ]: Start accepts. Automaton has 11 states. Word has length 17 [2018-06-22 15:15:05,886 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:15:05,887 INFO ]: With dead ends: 17 [2018-06-22 15:15:05,887 INFO ]: Without dead ends: 17 [2018-06-22 15:15:05,887 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 14 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=52, Invalid=130, Unknown=0, NotChecked=0, Total=182 [2018-06-22 15:15:05,887 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-22 15:15:05,891 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-22 15:15:05,891 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-22 15:15:05,892 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-22 15:15:05,892 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 17 [2018-06-22 15:15:05,892 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:15:05,892 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-22 15:15:05,892 INFO ]: Interpolant automaton has 11 states. [2018-06-22 15:15:05,892 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-22 15:15:05,893 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-22 15:15:05,893 INFO ]: Found error trace [2018-06-22 15:15:05,893 INFO ]: trace histogram [4, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:15:05,893 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:15:05,893 INFO ]: Analyzing trace with hash -2056434034, now seen corresponding path program 3 times [2018-06-22 15:15:05,893 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:15:05,893 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:15:05,894 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:05,894 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:15:05,894 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:05,925 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:06,365 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:15:06,365 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:15:06,365 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:15:06,372 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 15:15:06,416 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-22 15:15:06,416 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:06,420 INFO ]: Computing forward predicates... [2018-06-22 15:15:07,560 WARN ]: Spent 796.00 ms on a formula simplification. DAG size of input: 125 DAG size of output: 29 [2018-06-22 15:15:07,826 INFO ]: Checked inductivity of 21 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-22 15:15:07,854 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:15:07,854 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2018-06-22 15:15:07,855 INFO ]: Interpolant automaton has 15 states [2018-06-22 15:15:07,855 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-22 15:15:07,855 INFO ]: CoverageRelationStatistics Valid=42, Invalid=168, Unknown=0, NotChecked=0, Total=210 [2018-06-22 15:15:07,855 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 15 states. [2018-06-22 15:15:08,078 WARN ]: Spent 208.00 ms on a formula simplification. DAG size of input: 44 DAG size of output: 41 [2018-06-22 15:15:08,458 WARN ]: Spent 172.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 37 [2018-06-22 15:15:08,489 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:15:08,489 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 15:15:08,491 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 15:15:08,491 INFO ]: Start accepts. Automaton has 15 states. Word has length 21 [2018-06-22 15:15:08,491 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:15:08,491 INFO ]: With dead ends: 19 [2018-06-22 15:15:08,491 INFO ]: Without dead ends: 19 [2018-06-22 15:15:08,492 INFO ]: 0 DeclaredPredicates, 34 GetRequests, 16 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 42 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=82, Invalid=260, Unknown=0, NotChecked=0, Total=342 [2018-06-22 15:15:08,492 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 15:15:08,495 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 15:15:08,495 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 15:15:08,495 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 15:15:08,495 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 21 [2018-06-22 15:15:08,496 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:15:08,496 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 15:15:08,496 INFO ]: Interpolant automaton has 15 states. [2018-06-22 15:15:08,496 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 15:15:08,496 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 15:15:08,496 INFO ]: Found error trace [2018-06-22 15:15:08,496 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:15:08,497 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:15:08,497 INFO ]: Analyzing trace with hash -434924750, now seen corresponding path program 4 times [2018-06-22 15:15:08,497 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:15:08,497 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:15:08,498 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:08,498 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:15:08,498 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:08,536 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:09,639 WARN ]: Spent 965.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 23 [2018-06-22 15:15:09,888 WARN ]: Spent 157.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 12 [2018-06-22 15:15:10,040 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:15:10,040 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:15:10,040 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:15:10,047 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 15:15:10,093 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 15:15:10,093 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:10,097 INFO ]: Computing forward predicates... [2018-06-22 15:15:11,587 WARN ]: Spent 789.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 35 [2018-06-22 15:15:11,811 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 19 [2018-06-22 15:15:13,458 WARN ]: Spent 170.00 ms on a formula simplification. DAG size of input: 7 DAG size of output: 2 [2018-06-22 15:15:13,487 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 15:15:13,519 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:15:13,519 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 17 [2018-06-22 15:15:13,520 INFO ]: Interpolant automaton has 17 states [2018-06-22 15:15:13,520 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-22 15:15:13,520 INFO ]: CoverageRelationStatistics Valid=42, Invalid=230, Unknown=0, NotChecked=0, Total=272 [2018-06-22 15:15:13,520 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 17 states. [2018-06-22 15:15:13,766 WARN ]: Spent 103.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-22 15:15:14,973 WARN ]: Spent 905.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 52 [2018-06-22 15:15:15,332 WARN ]: Spent 331.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 29 [2018-06-22 15:15:15,535 WARN ]: Spent 186.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 23 [2018-06-22 15:15:15,727 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 45 [2018-06-22 15:15:15,941 WARN ]: Spent 191.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 51 [2018-06-22 15:15:15,976 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:15:15,976 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 15:15:15,977 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 15:15:15,977 INFO ]: Start accepts. Automaton has 17 states. Word has length 25 [2018-06-22 15:15:15,977 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:15:15,978 INFO ]: With dead ends: 21 [2018-06-22 15:15:15,978 INFO ]: Without dead ends: 21 [2018-06-22 15:15:15,978 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 20 SyntacticMatches, 1 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=107, Invalid=399, Unknown=0, NotChecked=0, Total=506 [2018-06-22 15:15:15,978 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 15:15:15,981 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 15:15:15,981 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 15:15:15,981 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 15:15:15,982 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 15:15:15,983 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:15:15,983 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 15:15:15,983 INFO ]: Interpolant automaton has 17 states. [2018-06-22 15:15:15,983 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 15:15:15,983 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 15:15:15,983 INFO ]: Found error trace [2018-06-22 15:15:15,984 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:15:15,984 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:15:15,984 INFO ]: Analyzing trace with hash 1986427350, now seen corresponding path program 5 times [2018-06-22 15:15:15,984 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:15:15,984 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:15:15,984 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:15,984 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:15:15,984 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:16,058 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:16,616 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:15:16,616 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:15:16,616 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:15:16,622 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 15:15:16,694 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-22 15:15:16,694 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:16,698 INFO ]: Computing forward predicates... [2018-06-22 15:15:25,568 WARN ]: Spent 7.79 s on a formula simplification. DAG size of input: 1014 DAG size of output: 63 [2018-06-22 15:15:27,509 WARN ]: Spent 1.36 s on a formula simplification. DAG size of input: 22 DAG size of output: 19 [2018-06-22 15:15:27,953 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 15:15:27,978 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:15:27,978 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 19 [2018-06-22 15:15:27,978 INFO ]: Interpolant automaton has 19 states [2018-06-22 15:15:27,978 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-22 15:15:27,978 INFO ]: CoverageRelationStatistics Valid=45, Invalid=297, Unknown=0, NotChecked=0, Total=342 [2018-06-22 15:15:27,979 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 19 states. [2018-06-22 15:15:28,608 WARN ]: Spent 587.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 63 [2018-06-22 15:15:28,813 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 77 DAG size of output: 18 [2018-06-22 15:15:29,025 WARN ]: Spent 182.00 ms on a formula simplification. DAG size of input: 79 DAG size of output: 26 [2018-06-22 15:15:29,361 WARN ]: Spent 311.00 ms on a formula simplification. DAG size of input: 80 DAG size of output: 32 [2018-06-22 15:15:29,529 WARN ]: Spent 145.00 ms on a formula simplification. DAG size of input: 81 DAG size of output: 29 [2018-06-22 15:15:30,176 WARN ]: Spent 623.00 ms on a formula simplification. DAG size of input: 82 DAG size of output: 40 [2018-06-22 15:15:30,213 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:15:30,213 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-22 15:15:30,221 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-22 15:15:30,221 INFO ]: Start accepts. Automaton has 19 states. Word has length 29 [2018-06-22 15:15:30,221 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:15:30,222 INFO ]: With dead ends: 23 [2018-06-22 15:15:30,222 INFO ]: Without dead ends: 23 [2018-06-22 15:15:30,222 INFO ]: 0 DeclaredPredicates, 49 GetRequests, 23 SyntacticMatches, 2 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 49 ImplicationChecksByTransitivity, 12.7s TimeCoverageRelationStatistics Valid=126, Invalid=524, Unknown=0, NotChecked=0, Total=650 [2018-06-22 15:15:30,223 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-22 15:15:30,226 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-22 15:15:30,226 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-22 15:15:30,226 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-22 15:15:30,226 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 29 [2018-06-22 15:15:30,227 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:15:30,227 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-22 15:15:30,227 INFO ]: Interpolant automaton has 19 states. [2018-06-22 15:15:30,227 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-22 15:15:30,227 INFO ]: Finished isEmpty. Found accepting run of length 34 [2018-06-22 15:15:30,227 INFO ]: Found error trace [2018-06-22 15:15:30,227 INFO ]: trace histogram [7, 6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:15:30,228 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:15:30,228 INFO ]: Analyzing trace with hash 800064122, now seen corresponding path program 6 times [2018-06-22 15:15:30,228 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:15:30,228 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:15:30,228 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:30,228 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:15:30,228 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:30,347 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:31,101 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:15:31,101 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:15:31,101 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:15:31,106 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 15:15:31,160 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-22 15:15:31,160 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:31,165 INFO ]: Computing forward predicates... [2018-06-22 15:15:31,502 WARN ]: Spent 131.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 31 [2018-06-22 15:15:33,682 WARN ]: Spent 1.78 s on a formula simplification. DAG size of input: 184 DAG size of output: 89 [2018-06-22 15:15:36,403 INFO ]: Checked inductivity of 78 backedges. 0 proven. 57 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-22 15:15:36,432 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 15:15:36,432 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 27 [2018-06-22 15:15:36,433 INFO ]: Interpolant automaton has 27 states [2018-06-22 15:15:36,433 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-22 15:15:36,433 INFO ]: CoverageRelationStatistics Valid=73, Invalid=629, Unknown=0, NotChecked=0, Total=702 [2018-06-22 15:15:36,433 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 27 states. [2018-06-22 15:15:37,567 WARN ]: Spent 1.09 s on a formula simplification. DAG size of input: 136 DAG size of output: 114 [2018-06-22 15:15:38,217 WARN ]: Spent 581.00 ms on a formula simplification. DAG size of input: 141 DAG size of output: 35 [2018-06-22 15:15:38,890 WARN ]: Spent 636.00 ms on a formula simplification. DAG size of input: 134 DAG size of output: 44 [2018-06-22 15:15:40,065 WARN ]: Spent 1.14 s on a formula simplification. DAG size of input: 140 DAG size of output: 42 [2018-06-22 15:15:40,560 WARN ]: Spent 449.00 ms on a formula simplification. DAG size of input: 133 DAG size of output: 43 [2018-06-22 15:15:41,674 WARN ]: Spent 1.07 s on a formula simplification. DAG size of input: 140 DAG size of output: 40 [2018-06-22 15:15:42,928 WARN ]: Spent 1.17 s on a formula simplification. DAG size of input: 140 DAG size of output: 94 [2018-06-22 15:15:42,971 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 15:15:42,971 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 15:15:42,972 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 15:15:42,972 INFO ]: Start accepts. Automaton has 27 states. Word has length 33 [2018-06-22 15:15:42,972 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 15:15:42,973 INFO ]: With dead ends: 25 [2018-06-22 15:15:42,973 INFO ]: Without dead ends: 25 [2018-06-22 15:15:42,974 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 22 SyntacticMatches, 1 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 133 ImplicationChecksByTransitivity, 10.1s TimeCoverageRelationStatistics Valid=198, Invalid=992, Unknown=0, NotChecked=0, Total=1190 [2018-06-22 15:15:42,974 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 15:15:42,978 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 15:15:42,978 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 15:15:42,979 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 15:15:42,979 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 33 [2018-06-22 15:15:42,979 INFO ]: Finished accepts. word is rejected. [2018-06-22 15:15:42,979 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 15:15:42,979 INFO ]: Interpolant automaton has 27 states. [2018-06-22 15:15:42,979 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 15:15:42,980 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 15:15:42,980 INFO ]: Found error trace [2018-06-22 15:15:42,980 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 15:15:42,980 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 15:15:42,980 INFO ]: Analyzing trace with hash -411423458, now seen corresponding path program 7 times [2018-06-22 15:15:42,980 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 15:15:42,980 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 15:15:42,981 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:42,981 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 15:15:42,981 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 15:15:43,024 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:43,235 WARN ]: Spent 111.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-22 15:15:43,891 WARN ]: Spent 609.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 23 [2018-06-22 15:15:44,415 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 15:15:44,415 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 15:15:44,415 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:15:44,422 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 15:15:44,460 INFO ]: Conjunction of SSA is unsat [2018-06-22 15:15:44,467 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-22 15:16:06,603 WARN ]: Removed 9 from assertion stack [2018-06-22 15:16:06,603 INFO ]: Timeout while computing interpolants [2018-06-22 15:16:06,804 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 15:16:06,804 WARN ]: Verification canceled [2018-06-22 15:16:06,807 WARN ]: Timeout [2018-06-22 15:16:06,807 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 03:16:06 BoogieIcfgContainer [2018-06-22 15:16:06,807 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 15:16:06,808 INFO ]: Toolchain (without parser) took 64150.90 ms. Allocated memory was 299.9 MB in the beginning and 835.2 MB in the end (delta: 535.3 MB). Free memory was 254.3 MB in the beginning and 677.8 MB in the end (delta: -423.5 MB). Peak memory consumption was 625.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:16:06,809 INFO ]: SmtParser took 0.05 ms. Allocated memory is still 299.9 MB. Free memory is still 265.4 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 15:16:06,809 INFO ]: ChcToBoogie took 43.80 ms. Allocated memory is still 299.9 MB. Free memory was 253.3 MB in the beginning and 252.3 MB in the end (delta: 996.2 kB). Peak memory consumption was 996.2 kB. Max. memory is 3.6 GB. [2018-06-22 15:16:06,810 INFO ]: Boogie Preprocessor took 56.82 ms. Allocated memory is still 299.9 MB. Free memory was 252.3 MB in the beginning and 250.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:16:06,810 INFO ]: RCFGBuilder took 319.66 ms. Allocated memory is still 299.9 MB. Free memory was 250.3 MB in the beginning and 242.3 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:16:06,811 INFO ]: TraceAbstraction took 63722.04 ms. Allocated memory was 299.9 MB in the beginning and 835.2 MB in the end (delta: 535.3 MB). Free memory was 241.3 MB in the beginning and 677.8 MB in the end (delta: -436.4 MB). Peak memory consumption was 612.0 MB. Max. memory is 3.6 GB. [2018-06-22 15:16:06,815 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.05 ms. Allocated memory is still 299.9 MB. Free memory is still 265.4 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 43.80 ms. Allocated memory is still 299.9 MB. Free memory was 253.3 MB in the beginning and 252.3 MB in the end (delta: 996.2 kB). Peak memory consumption was 996.2 kB. Max. memory is 3.6 GB. * Boogie Preprocessor took 56.82 ms. Allocated memory is still 299.9 MB. Free memory was 252.3 MB in the beginning and 250.3 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 319.66 ms. Allocated memory is still 299.9 MB. Free memory was 250.3 MB in the beginning and 242.3 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 63722.04 ms. Allocated memory was 299.9 MB in the beginning and 835.2 MB in the end (delta: 535.3 MB). Free memory was 241.3 MB in the beginning and 677.8 MB in the end (delta: -436.4 MB). Peak memory consumption was 612.0 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 38 with TraceHistMax 8, while TraceCheckSpWp was constructing forward predicates, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 2152. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 63.6s OverallTime, 8 OverallIterations, 8 TraceHistogramMax, 12.4s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 86 SDtfs, 198 SDslu, 468 SDs, 0 SdLazy, 385 SolverSat, 249 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.7s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 230 GetRequests, 111 SyntacticMatches, 6 SemanticMatches, 113 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 272 ImplicationChecksByTransitivity, 32.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=25occurred in iteration=7, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.6s SatisfiabilityAnalysisTime, 26.3s InterpolantComputationTime, 285 NumberOfCodeBlocks, 285 NumberOfCodeBlocksAsserted, 28 NumberOfCheckSat, 272 ConstructedInterpolants, 0 QuantifiedInterpolants, 2282128 SizeOfPredicates, 271 NumberOfNonLiveVariables, 927 ConjunctsInSsa, 213 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 112/406 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/nested4.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_15-16-06-826.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/nested4.c.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_15-16-06-826.csv Completed graceful shutdown